package com.example.leetcode.bfs;

import java.util.*;

public class leetcode752 {
    public static void main(String[] args) {
        String[] deadends = new String[]{"0201", "0101", "0102", "1212", "2002"};
        String target = "0202";

        Solution solution = new Solution();
        System.out.println(solution.openLock(deadends, target));
    }

    /**
     * 双向BFS
     */
    static class Solution {
        public int openLock(String[] deadends, String target) {
            String start = "0000";
            if (start.equals(target)) {
                return 0; // 目标是起点，无需操作
            }

            Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
            if (deadSet.contains(start) || deadSet.contains(target)) {
                return -1;
            }

            Set<String> visited = new HashSet<>();
            Set<String> beginSet = new HashSet<>();
            Set<String> endSet = new HashSet<>();

            beginSet.add(start);
            endSet.add(target);
            visited.add(start);

            int steps = 0;

            while (!beginSet.isEmpty() && !endSet.isEmpty()) {
                if (beginSet.size() > endSet.size()) {
                    Set<String> temp = beginSet;
                    beginSet = endSet;
                    endSet = temp;
                }

                Set<String> tempSet = new HashSet<>();

                for (String code : beginSet) {
                    for (String next : getNextStates(code)) {
                        // 扩散之后判断是否相遇
                        if (endSet.contains(next)) {
                            return steps + 1; // 这是相遇点！
                        }

                        if (!visited.contains(next) && !deadSet.contains(next)) {
                            tempSet.add(next);
                            visited.add(next);
                        }
                    }
                }

                beginSet = tempSet;
                steps++;
            }

            return -1;
        }

        private List<String> getNextStates(String s) {
            List<String> result = new ArrayList<>();
            char[] chs = s.toCharArray();

            for (int i = 0; i < 4; i++) {
                char original = chs[i];

                // 向上拨
                chs[i] = original == '9' ? '0' : (char) (original + 1);
                result.add(new String(chs));

                // 向下拨
                chs[i] = original == '0' ? '9' : (char) (original - 1);
                result.add(new String(chs));

                // 复原
                chs[i] = original;
            }

            return result;
        }
    }


//    static class Solution {
//        public int openLock(String[] deadends, String target) {
//            Set<String> deadSet = new HashSet<>(Arrays.asList(deadends));
//            Set<String> visited = new HashSet<>();
//            Queue<String> queue = new LinkedList<>();
//
//            String start = "0000";
//            if (deadSet.contains(start)) return -1;
//
//            queue.offer(start);
//            visited.add(start);
//            int steps = 0;
//
//            while (!queue.isEmpty()) {
//                int size = queue.size();
//
//                for (int i = 0; i < size; i++) {
//                    String curr = queue.poll();
//                    if (curr.equals(target)) return steps;
//
//                    for (String next : getNextStates(curr)) {
//                        if (!deadSet.contains(next) && !visited.contains(next)) {
//                            visited.add(next);
//                            queue.offer(next);
//                        }
//                    }
//                }
//
//                steps++;
//            }
//
//            return -1;
//        }
//
//        private List<String> getNextStates(String s) {
//            List<String> result = new ArrayList<>();
//            char[] chs = s.toCharArray();
//
//            for (int i = 0; i < 4; i++) {
//                char original = chs[i];
//
//                // 向上拨
//                chs[i] = original == '9' ? '0' : (char) (original + 1);
//                result.add(new String(chs));
//
//                // 向下拨
//                chs[i] = original == '0' ? '9' : (char) (original - 1);
//                result.add(new String(chs));
//
//                // 恢复原状
//                chs[i] = original;
//            }
//
//            return result;
//        }
//    }


}
